package com.cn.algorithm02.class06;

import com.cn.algorithm02.class01.CodeUtil;

/***
 * @author: hels
 * @description:快速排序：时间复杂度O(N)，
 **/
public class C02_QuickSort {
    public static void main(String[] args) {
        int[] arr = {2,3,1,-1,-6,4,7,-3,3,2,8,3,-5,3,3};
//        quick2(arr);
        int[] s = quick2(arr);
        for (int i :s) {
            System.out.print(i + " ");
        }
        System.out.println("===");
        CodeUtil.printArray(arr);
    }

    // 小于等于的放在左边，大于的放在右边； 以最右边的为基准
    public static void quick1(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        int index = -1; // 左边区域下标
        int pointer = 0; // 移动指针
        int basic = arr[arr.length - 1];
        // 基准数为arr[arr.length - 1]
        while (pointer < arr.length) {
            if (arr[pointer] <= basic) {
                CodeUtil.swap(arr, ++index, pointer++);
            } else {
                pointer++;
            }
        }
    }
    /*
    小于左边，基准数中间，大于右边。基准数为最右边
     */
    public static int[] quick2(int[] arr) {
        if(arr == null || arr.length < 2) {
            return new int[]{-1,-1};
        }
        // length >=2
        int basic = arr[arr.length - 1];
        int left = -1;
        int right = arr.length;
        int pointer = 0;
        //
        while (pointer < right) {
            if (arr[pointer] < basic) {
                CodeUtil.swap(arr, pointer++, ++left);
            } else if (arr[pointer] > basic) {
                CodeUtil.swap(arr,pointer, --right);
            } else {
                pointer++;
            }
        }
        return new int[]{left+1, right-1};
    }

}
